class MinHeap {
  constructor() {
    this.heap = [];
  }

  // 交换父子节点的值
  swap(parentIndex, childIndex) {
    const tempParent = this.heap[parentIndex];
    this.heap[parentIndex] = this.heap[childIndex];
    this.heap[childIndex] = tempParent;
  }

  getParentIndex(i) {
    return Math.floor((i - 1) / 2);
  }

  getLeftIndex(i) {
    return i * 2 + 1;
  }

  getRightIndex(i) {
    return i * 2 + 2;
  }

  // 上移操作: 将值和父节点进行交换, 直到父节点小于等于这个插入的值
  shiftUp(index) {
    if (index == 0) return;
    const parentIndex = this.getParentIndex(index);
    if (this.heap[parentIndex] > this.heap[index]) {
      this.swap(parentIndex, index);
      // 递归上移的操作
      this.shiftUp(parentIndex);
    }
  }

  shiftDown(index) {
    const leftIndex = this.getLeftIndex(index);
    const rightIndex = this.getRightIndex(index);
    if (this.heap[leftIndex] < this.heap[index]) {
      this.swap(leftIndex, index);
      this.shiftDown(leftIndex);
    }
    if (this.heap[rightIndex] < this.heap[index]) {
      this.swap(rightIndex, index);
      this.shiftDown(rightIndex);
    }
  }

  insert(value) {
    this.heap.push(value);
    // 上移操作
    this.shiftUp(this.heap.length - 1);
  }

  // 删除堆顶
  pop() {
    // 将最后一个值放到堆顶, 保证后续的结构不变
    this.heap[0] = this.heap.pop();
    this.shiftDown(0);
  }

  // 获取堆顶
  peek() {
    return this.heap[0];
  }

  // 获取长度
  size() {
    return this.heap.length;
  }
}

const h = new MinHeap();
h.insert(3);
h.insert(2);
h.insert(1);
console.log(h);
